Fast iterative algorithms are often used for solving Method of Moments (MoM) systems having a large number of unknowns, to determine current distribution and other parameters. The most commonly used fast methods include the fast multipole method (FMM), the precorrected fast Fourier transform (PFFT), and low-rank QR compression methods. These methods reduce the O(N2) memory and time requirements to O(N log N) by compressing the dense MoM system so as to exploit the physics of Green's function interactions.
FFT-based techniques for solving such problems are efficient for space-filling and uniform structures, but their performance substantially degrades for non-uniformly distributed structures, due to the inherent need to employ a uniform global grid. For solving arbitrarily-shaped structures, which is a typical requirement, FMM and QR techniques are better suited than FFT techniques. The FMM and QR approaches use oct-tree based geometric decomposition and employ multipole operators or Modified Gram-Schmidt (MGS) orthogonalization to compress interactions between far-field cube elements of the oct-tree representation. The fast multilevel algorithms have been used to solve the electric field integral equation (EFIE), magnetic field integral equation (MFIE) and combined field integral equation (CFIE).
However, neither the FMM technique nor the QR technique can be used at all frequencies. Specifically, in the FMM technique, the translation operator becomes near singular at low frequencies, producing unacceptably inaccurate results and making it inapplicable to electrically small structures, e.g., in modeling electronic packages and interconnects. In contrast, QR based methods become unusable at higher frequencies, because the QR compression scheme becomes inefficient for oscillating kernels. In addition, the QR technique is optimally usable with electrically small structures. A paper by D. Gope, S. Chakraborty, and V. Jandhyala entitled “A Fast Parasitic Extractor Based on Low-Rank Multilevel Matrix Compression for Conductor and Dielectric Modeling in Microelectronics and MEMS” presented at the June 2004 Design Automation Conference teaches combining the multilevel oct-tree structure that is common to FMM approaches, with the QR compression technique to achieve some optimization in solving for parasitic capacitance (DC), which is the type of solution for which the QR technique is suited. However, this approach cannot be used for solving a general broadband system that may have both large electrical structures operating at higher frequencies and small electrical structures operating at low frequencies. Using only QR techniques to solve such a system is impractical, because the processing time and effort becomes prohibitive when a relatively large system must be divided into an oct-tree structure comprising only such smaller portions.
There are other relative advantages and disadvantages for these methods. For example, the QR method has a higher setup time, but a lower matrix-vector product time, and can be easily parallelized, whereas FMM has a lower setup time, but has a higher matrix-vector product time. Also, the QR method is kernel independent, unlike FMM, which depends on the availability of analytic multipole operators. FMM is ideally suited for problems with fewer RHS vectors, while the QR method is better for systems with a larger number of RHS vectors. Thus, the QR method is best applied for achieving a solution for elements operating at low frequencies, while the FMM method is preferred for achieving a solution for elements operating at high frequencies.
Systems that include both electrically small elements operating at low frequencies and electrically large elements operating at higher frequencies are relatively common. Clearly, it would be desirable to develop an approach to solving such systems. The new approach should be a combination of these two methods, should be stable at all frequencies of the system, and be independent of the electrical size of the problem. Researchers have proposed a low-frequency FMM (LF-MLFMA), which removes the breakdown of the translator by renormalization of the FMM operators and can be used for treating electrically small structures, but this proposed technique does not provide the accuracy of the QR approach for low frequency and small electrical elements, because two different kinds of FMM operators are required and integration with the higher level FMM operators is difficult during translating from lower to higher levels. Accordingly, a better and more efficient approach is needed that retains the benefits and advantages of both the FMM and QR techniques, and which also provides for the interaction between FMM and QR elements in the solution that is achieved.